package algorithm.dynamicProgramming.p416;

import java.util.Arrays;

/**
 * 416. 分割等和子集
 */
class Solution_v2 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum % 2 != 0) {
            return false;
        }

        int c = sum / 2;
        // 容量分别为[0...c]的背包是否能被填满
        boolean[] memo = new boolean[c + 1];

        // 尝试用第一个数去填满背包
        for (int i = 0; i <= c; i++) {
            memo[i] = nums[0] == i;
        }

        // 每次循环多考虑一个物品
        for (int i = 1; i < nums.length; i++) {
            // 尝试去填满不同容量的背包
            for (int j = c; j >= nums[i]; j--) {
                memo[j] = memo[j] || memo[j - nums[i]];
            }
        }

        // 容量为c的背包的状态就是需要的结果
        return memo[c];
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v2().canPartition(new int[]{1, 5, 11, 5}));
    }
}